package com.person.leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
  * 31.下一个排列
  * 2022-09-29 15:07:01
**/
public class Sequence_0031_NextPermutation {
    public static void main(String[] args) {
        Solution solution = new Sequence_0031_NextPermutation().new Solution();
    }
    //相当于进位,后面的变为升序
    //寻找当前点后面的一定为降序,否则没有
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            //找到非倒序的节点
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.length - 1;
                //替换最接近的节点
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        public void reverse(int[] nums, int start) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}